package madixin.t127;

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>();
        for (String word : wordList) {
            wordSet.add(word);
        }
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        int time = 0;
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        while (!queue.isEmpty()) {
            time++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (int j = 0; j < beginWord.length(); j++) {
                    for (char h = 'a'; h <= 'z'; h++) {
                        StringBuilder sb = new StringBuilder(cur);
                        sb.setCharAt(j, h);
                        if (sb.toString().equals(endWord)) {
                            System.out.println(sb.toString() + time);
                            return time + 1;
                        }
                        if (!wordSet.contains(sb.toString())) {
                            continue;
                        }
                        System.out.println(sb.toString() + time);
                        wordSet.remove(sb.toString());
                        queue.add(sb.toString());
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.ladderLength("hit", "cog", Arrays.asList(new String[]{"hot", "dot", "dog", "lot", "log", "cog"})));
    }
}